package huawei.checkandset;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/evaluate-division/
 * [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/evaluate-division
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class J399 {
    public static void main(String[] args) {
        List<List<String>> equations = new ArrayList<>();
        ArrayList<String> tmp = new ArrayList<>();
        tmp.add("a");
        tmp.add("b");
        equations.add(tmp);
        tmp = new ArrayList<>();
        tmp.add("b");
        tmp.add("c");
        equations.add(tmp);

        List<List<String>> queries = new ArrayList<List<String>>();
        tmp = new ArrayList<>();
        tmp.add("a");
        tmp.add("c");
        queries.add(tmp);
        tmp = new ArrayList<>();
        tmp.add("b");
        tmp.add("a");
        queries.add(tmp);
        tmp = new ArrayList<>();
        tmp.add("a");
        tmp.add("e");
        queries.add(tmp);
        tmp = new ArrayList<>();
        tmp.add("a");
        tmp.add("a");
        queries.add(tmp);
        tmp = new ArrayList<>();
        tmp.add("x");
        tmp.add("x");
        queries.add(tmp);
        //[6.00000,0.50000,-1.00000,1.00000,-1.00000]
        System.out.println(Arrays.toString(new J399().calcEquation(equations, new double[]{2, 3}, queries)));
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        HashMap<String, Integer> map = new HashMap<>();
        int len = 0;
        for (List<String> equ : equations) {
            for (String eq : equ) {
                if (map.get(eq) == null) {
                    map.put(eq, len++);
                }
            }
        }
        parents = new int[len];
        vals = new double[len];
        Arrays.fill(vals, 1d);
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
        for (int i = 0; i < values.length; i++) {
            List<String> equ = equations.get(i);
            int a = map.get(equ.get(0));
            int b = map.get(equ.get(1));
            merge(a, b, values[i]);
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            res[i] = div(map.get(queries.get(i).get(0)), map.get((queries.get(i).get(1))));
        }

        return res;
    }

    private double div(Integer a, Integer b) {
        if (a == null || b == null) {
            return -1d;
        }
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot != bRoot) {
            return -1d;
        }
        return vals[a] / vals[b];
    }
    // 做了压缩,最大三层
    private int find(int i) {
        if (i != parents[i]) {
            int origin = parents[i];
            if(origin!=parents[origin]){
                parents[i]=parents[origin];
                vals[i]=vals[i]*vals[origin];
            }
        }
        return parents[i];
    }

    private void merge(int a, int b, double value) {
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot) {
            return;
        }
        parents[aRoot] = bRoot;
        vals[aRoot] = vals[b] * value/vals[a];
        System.out.println(Arrays.toString(parents));
        System.out.println(Arrays.toString(vals));
    }

    int[] parents;
    double[] vals;
}
